package t_198

import "sort"

func rob(nums []int) int {

	// 分为偷与不偷
	// f(n)= max(f(n-1),f(n-2)+nums[n-2])

	l := len(nums)
	if l < 3 {
		temp := nums
		sort.Ints(temp)
		return temp[l-1]
	}

	l2 := 0
	l1 := nums[0]
	sum := 0
	for i := 2; i <= l; i++ {
		sum = max(l1, l2+nums[i-1])
		l1, l2 = sum, l1
	}

	return sum
}

func max(a, b int) int {
	if a < b {
		return b
	}

	return a
}

func rob2(nums []int) int {
	// 首尾不能连续

	// f(n)= max(f(n-1),f(n-2)+nums[n-2])

	// 取f(1)不能取f(n)

	l := len(nums)
	if l < 3 {
		return 0
	}

	l2 := 0
	l1 := nums[0]
	sum := 0
	for i := 2; i <= l; i++ {
		sum = max(l1, l2+nums[i-1])
		l1, l2 = sum, l1
	}

	rand2s := 0
	for i := 1; i <= l; i++ {
		rand2s = max(l1, l2+nums[i-1])
		l1, l2 = rand2s, l1
	}

	return rand2s - sum
}

func deleteAndEarn(nums []int) int {
	maxVal := 0
	for _, val := range nums {
		maxVal = max(maxVal, val)
	}
	sum := make([]int, maxVal+1)
	for _, val := range nums {
		sum[val] += val
	}
	return rob(sum)
}

func eatenApples(apples []int, days []int) int {

	// f(n) = f(n-1)+offset-n

	dp := make([]int, len(apples))
	for i := 0; i < len(apples); i++ {
		dp[i] = i + min(apples[i], days[i])
	}

	offset := 0

	sum := 0
	for i := 0; i < len(dp); i++ {

		if offset < dp[i] {
			offset = dp[i]
			sum += offset - i
		}
	}

	return sum
}

func min(a, b int) int {
	if a > b {
		return b
	}

	return a
}
